﻿#pragma once

#include <assert.h>
#include <iostream>

#include "Matrix.h"

// Permutations algorithm from:
// http://rain.ifmo.ru/cat/view.php/theory/combinations/combinations1-2004
//
//  1  procedure B(m, i);
//  2  begin
//  3      if (m mod 2 = 0) and (m > 2) then
//  4          if i < m − 1 then B := i
//  5          else B := m − 2
//  6      else B := m − 1
//  7  end;
//
//  8  procedure PERM(m);
//  9  begin
//  10      if m = 1 then
//  11          write(P[1], …, P[n])
//  12      else
//  13          for i := 1 to m do
//  14              begin PERM(m − 1);
//  15                  if i < m then P[B(m, i)] :=: P[m]
//  16              end
//  17  end;
//
//  18  begin
//  19      for i := 1 to n do P[i] :=: i;
//  20      PERM(n)
//  21  end


struct PermuteMetaData;
void Permute(size_t dataSize, size_t* data);
void Permute(size_t m, size_t* data, PermuteMetaData& metaData);
size_t B(size_t m, size_t i);

struct PermuteMetaData
{
    PermuteMetaData(size_t dataSize) : m_dataSize(dataSize), m_permutationCounter(0)
    {
    }

    size_t m_dataSize;
    size_t m_permutationCounter;
};

void Permute(size_t dataSize, size_t* data)
{
    PermuteMetaData metaData(dataSize);
    Permute(dataSize, data, metaData);
}

void PrintData(size_t dataSize, size_t* data, size_t counter)
{
    std::cout << counter << ": ";

    for (size_t ii = 0; ii < dataSize; ++ii)
    {
        std::cout << data[ii] << " ";
    }

    std::cout << '\n';
}

void Permute(size_t m, size_t* data, PermuteMetaData& metaData)
{
    if (m == 1)
    {
        PrintData(metaData.m_dataSize, data, ++metaData.m_permutationCounter);
    }
    else
    {
        for (size_t i = 0; i < m; ++i)
        {
            Permute(m - 1, data, metaData);
            
            if (i < m - 1) 
            {
                std::swap(data[B(m, i)], data[m - 1]);
            }
        }
    }
}

size_t B(size_t m, size_t i)
{
    if (m % 2 == 0 && m > 2)
    {
        return (i < m - 2) ? i : m - 3;
    }
    else
    {
        return m - 2;
    }
}

// Permutations algorithm from:
// http://rain.ifmo.ru/cat/view.php/theory/combinations/combinations1-2004
//
//   1  begin
//   2    for i := 1 to n do
//   3        begin P[i] := i; C[i] := 1; PR[i] := true; 
//   4        end;
//   5    C[n] := 0;
//   6    write(P[1], …, P[n]);
//   7    i := 1;
//   8    while i < n do
//   9        begin i := 1; x := 0;
//  10            while C[i] = n − i + 1 do
//  11                begin PR[i] := not PR[i]; C[i] := 1;
//  12                    if PR[i] then x := x + 1;
//  13                    i := i + 1;
//  14                end;
//  15            if i < n then
//  16                begin
//  17                    if PR[i] then k := C[i] + x;
//  18                    else k := n − i + 1 − C[i] + x;
//  19                    P[k] :=: P[k + 1];
//  20                    write(P[1], …, P[n]);
//  21                    C[i] := C[i] + 1
//  22                end
//  23      end
//  24  end
//

void PermuteFast(size_t n)
{
    size_t* data = new size_t[n];
    size_t* relativePosition = new size_t[n];
    bool* forward = new bool[n];

    for (size_t i = 1; i <= n; ++i)
    {
        data[i-1] = i;
        relativePosition[i-1] = 1;
        forward[i-1] = true;
    }

    relativePosition[n-1] = 0;

    size_t counter = 1;

    PrintData(n, data, counter++);

    size_t i = 0;

    while (i + 1 < n)
    {
        i = 0;
        size_t x = 0;

        while (relativePosition[i] == n - i)
        {
            forward[i] = !forward[i];
            relativePosition[i] = 1;

            if (forward[i])
            {
                ++x;
            }

            ++i;
        }

        if (i + 1 < n)
        {
            size_t k = forward[i] ? relativePosition[i] + x : n - i - relativePosition[i] + x;
            std::swap(data[k-1], data[k]);
            PrintData(n, data, counter++);
            ++relativePosition[i];
        }
    }
}